package utils;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.SortedSet;

import model.ModelParameters;
import model.TableInformation;

public class BackboneCreator {
	
	private static Pair<int[], Integer> findGreedyBackboneOfSizeNRecursive(int n, int num_visible_cols, int num_hidden_cols, int[] prev_backbone,
			List<Map.Entry<IntPair, Integer> > sorted_col_adj_pairs, int next_pair, int root, int prev_set_cols, int[] hidden_col_pars) {
		int[] backbone = prev_backbone.clone();
		
		Pair<int[], Integer> best_full_backbone = null;
		for (int i = next_pair; i < sorted_col_adj_pairs.size(); i++) {
			int score = 0;
			int set_cols = prev_set_cols;
			for (int j = i; j < sorted_col_adj_pairs.size(); j++) {
				Map.Entry<IntPair, Integer> pair = sorted_col_adj_pairs.get(j);
				IntPair col_pair = pair.getKey();
				for (int k = 0; k < backbone.length; k++) {
					System.out.print(backbone[k] + " ");
				}
				System.out.println();
				for (int k = 0; k < hidden_col_pars.length; k++) {
					System.out.print(hidden_col_pars[k] + " ");
				}
				System.out.println();
				System.out.println(col_pair);
				int subj_col = col_pair.getFirst();
				int hidden_subj_col_par = -2;
				if (subj_col >= num_visible_cols) {
					if (subj_col == (num_visible_cols * 2)) {
						hidden_subj_col_par = -1;
					} else {
						hidden_subj_col_par = subj_col - num_visible_cols;
					}
					System.out.println("hidden subj col par " + hidden_subj_col_par);
					subj_col = num_visible_cols;
				}
				if (subj_col >= n) {
					continue;
				}
				int obj_col = col_pair.getSecond();
				if (obj_col >= n) {
					continue;
				}
				if (subj_col == -1 && root != -2) {
					continue;
				}
				if (subj_col >= num_visible_cols) {
					if (backbone[obj_col] != -2) {
						continue;
					}
					Pair<int[], Integer> best_backbone = null;
					int best_hidden_col = -2;
					for (int h = 0; h < num_hidden_cols; h++) {
						int hidden_subj_col = num_visible_cols + h;
						if (hidden_col_pars[h] == -2) {
							hidden_col_pars[h] = hidden_subj_col_par;
						} else if (hidden_col_pars[h] != hidden_subj_col_par) {
							continue;
						}
						backbone[obj_col] = hidden_subj_col;
						score += pair.getValue().intValue();
						Pair<int[], Integer> full_backbone = findGreedyBackboneOfSizeNRecursive(n, num_visible_cols, num_hidden_cols,
								backbone, sorted_col_adj_pairs, (i + 1), root, (set_cols + 1), hidden_col_pars);
						if (full_backbone != null) {
							if (best_backbone == null) {
								best_backbone = full_backbone;
								best_hidden_col = h;
							} else if (best_backbone.getSecond() < full_backbone.getSecond()) {
								best_backbone = full_backbone;
								best_hidden_col = h;
							}
						}
						hidden_col_pars[h] = -2;
					}
					if (best_backbone != null) {
						hidden_col_pars[best_hidden_col] = hidden_subj_col_par;
						return new Pair<int[], Integer>(best_backbone.getFirst(), best_backbone.getSecond() + score);
					}
					backbone[obj_col] = -2;
				} else if (obj_col >= num_visible_cols) {
					Pair<int[], Integer> best_backbone = null;
					int best_hidden_col = -2;
					for (int h = 0; h < num_hidden_cols; h++) {
						int hidden_obj_col = num_visible_cols + h;
						if (subj_col == -1) {
							root = num_visible_cols + h;
						}
						if (backbone[hidden_obj_col] != -2) {
							continue;
						}
						hidden_col_pars[h] = subj_col;
						System.out.println("hidden col " + hidden_col_pars[h]);
						backbone[hidden_obj_col] = subj_col;
						score += pair.getValue().intValue();
						Pair<int[], Integer> full_backbone = findGreedyBackboneOfSizeNRecursive(n, num_visible_cols, num_hidden_cols,
								backbone, sorted_col_adj_pairs, (i + 1), root, (set_cols + 1), hidden_col_pars);
						if (full_backbone != null) {
							if (best_backbone == null) {
								best_backbone = full_backbone;
								best_hidden_col = h;
							} else if (best_backbone.getSecond() < full_backbone.getSecond()) {
								best_backbone = full_backbone;
								best_hidden_col = h;
							}
						}
						backbone[hidden_obj_col] = -2;
						hidden_col_pars[h] = -2;
					}
					if (best_backbone != null) {
						hidden_col_pars[best_hidden_col] = subj_col;
						return new Pair<int[], Integer>(best_backbone.getFirst(), best_backbone.getSecond() + score);
					}
				} else {
					if (subj_col == -1) {
						root = obj_col;
					}
					if (backbone[obj_col] != -2) {
						continue;
					} else {
						backbone[obj_col] = subj_col;
						score += pair.getValue().intValue();
					}	
				}
				set_cols++;
				if (set_cols == backbone.length) {
					break;
				}
			}
			if (isOneTree(backbone)) {
				if (best_full_backbone == null || best_full_backbone.getSecond() < score) {
					best_full_backbone = new Pair<int[], Integer>(backbone, score); 
				}
			}
			set_cols = 0;
			backbone = prev_backbone.clone();
		}
		if (best_full_backbone == null) {
			return null;
		}
		backbone = best_full_backbone.getFirst();
		for (int c = 0; c < backbone.length; c++) {
			if (backbone[c] == -2) {
				backbone[c] = root;
			}
		}
		return new Pair<int[], Integer>(backbone, best_full_backbone.getSecond());
	}

	public static ArrayList<int[]> findGreedyBackbonesOfSizeN(int n, ModelParameters model_params) {
		ArrayList<int[]> backbones = new ArrayList<int[]>();
		for (int root = 0; root < n; root++) {
			if (model_params.getTableInformation().isLeafColumn(root)) {
				continue;
			}
			int[] backbone = new int[n];
			for (int c = 0; c < backbone.length; c++) {
				backbone[c] = -2;
			}
			backbone[root] = -1;
 			System.out.println("n: " + n);
			int num_visible_cols = model_params.getTableInformation().numVisibleCols();
			int hidden_col = model_params.getTableInformation().numVisibleCols();
			int num_hidden_cols = n - hidden_col;
			List<Map.Entry<IntPair, Integer> > sorted_col_adj_pairs = model_params.getSortedAdjColumnPairs();
	//		List<Map.Entry<IntPair, Integer> > sorted_col_adj_pairs = new ArrayList<Map.Entry<IntPair, Integer> >();
	//		sorted_col_adj_pairs.addAll(sorted_col_adj_pairs_set);
			for (Map.Entry<IntPair, Integer> pair : sorted_col_adj_pairs) {
				System.out.println(pair.getKey() + " " + pair.getValue());
			}
			int[] hidden_col_pars = new int[num_hidden_cols];
			for (int i = 0; i < num_hidden_cols; i++) {
				hidden_col_pars[i] = -2;
			}
			if (root >= num_visible_cols) {
				hidden_col_pars[root - num_visible_cols] = -1;
			}
			Pair<int[], Integer> backbone_pair = findGreedyBackboneOfSizeNRecursive(n, num_visible_cols, num_hidden_cols, backbone,
					sorted_col_adj_pairs, 0, root, 0, hidden_col_pars);
			if (backbone_pair == null) {
				continue;
			}
			backbone = backbone_pair.getFirst();
			for (int c = 0; c < backbone.length; c++) {
				System.out.print(backbone[c] + " ");
			}
			System.out.println();
			backbones.add(backbone);
		}
		return backbones;
	}
	
	public static boolean isOneTree(int[] backbone) {
		for (int c = 0; c < backbone.length; c++) {
			int root = findRoot(backbone, c, 0);
			if (root == -1) {
				return false;
			}
			if (root == c) {
				continue;
			}
			if (backbone[root] == -2) {
				return false;
			}
		}
		return true;
	}
	
	public static int findRoot(int[] backbone, int leaf, int rec_cnt) {
		int par = backbone[leaf];
		if (par < 0) {
			return leaf;
		}
		if (rec_cnt == backbone.length) {
			return -1;
		}
		return findRoot(backbone, par, (rec_cnt + 1));
	}
	
	public static ArrayList<int[]> findNBestBackbonesOfSizeN(int n, int[] column_is_leaf, TableInformation table_info) {
		return null;
	}
	public static ArrayList<int[]> findAllBackbonesOfSizeN(int num_cols, int[] column_is_leaf) {
		ArrayList<int[]> backbones = new ArrayList<int[]>();
		int num_non_leaves = 0;
		
		if (column_is_leaf == null) {
			column_is_leaf = new int[num_cols];
			for (int c = 0; c < num_cols; c++) {
				column_is_leaf[c] = 0;
			}
		} else {
			for (int c = 0; c < num_cols; c++) {
				if (column_is_leaf[c] == -1) {
					num_non_leaves++;
				}
			}
		}
		
		if (num_cols == 1) {
			backbones.add(new int[]{ -1});
			return backbones;
		}
		
		for (int col = 0; col < num_cols; col++) {
			if (column_is_leaf[col] == 1) {
				continue;
			}
			int[] backbone = new int[num_cols];
			int[] level = new int[num_cols];

			for (int c = 0; c < num_cols; c++) {
				// A value of -2 means that the parent of that vertex has not yet been set.
				backbone[c] = -2;
				level[c] = 1;
			}
			// A value of -1 means that column is the root.
			backbone[col] = -1;
			
			findAllBackbonesOfSizeNRecursiveHelper(backbones, col, num_cols, column_is_leaf, backbone, level, num_non_leaves);
		}
		
		return backbones;
	}
	
	private static void findAllBackbonesOfSizeNRecursiveHelper(ArrayList<int[]> backbones, int par, int num_cols, 
			int[] column_is_leaf, int[] backbone, int[] level, int num_non_leaves) {
		int max_chd = -1;
		for (int p = 0; p < num_cols; p++) {
			if (backbone[p] == par && p > max_chd) {
				max_chd = p;
			}
		}
		for (int chd = 0; chd < num_cols; chd++) {
			if (par == chd || backbone[chd] != -2) {
				continue;
			}
			if (chd < max_chd) {
				continue;
			}
			int[] new_backbone = backbone.clone();
			int[] new_level = level.clone();
			new_backbone[chd] = par;
			new_level[chd] = new_level[par] + 1;
			
			boolean found = false;
			int[] has_chd = column_is_leaf.clone();
			int max_level = -1;
			for (int col = 0; col < num_cols; col++) {
				if (new_level[col] > max_level) {
					max_level = new_level[col];
				}
				if (new_backbone[col] == -2) {
					found = true;
					break;
				} else if (new_backbone[col] != -1) {
					has_chd[new_backbone[col]]++;
				}
			}
			if (!found) {
				if (num_non_leaves != 0) {
					int c;
					for (c = 0; c < num_cols; c++) {
						if (has_chd[c] == -1) {
							break;
						}
					}
					if (c == num_cols) {
						backbones.add(new_backbone);
					}
				} else {
					backbones.add(new_backbone);
				}
			} else {
				for (int new_par = 0; new_par < num_cols; new_par++) {
					if (column_is_leaf[new_par] == 1) {
						continue;
					} else if (new_backbone[new_par] == -2 || new_level[new_par] + 1 < max_level) {
						continue;
					}
					findAllBackbonesOfSizeNRecursiveHelper(backbones, new_par, num_cols, column_is_leaf,
							new_backbone, new_level, num_non_leaves);
				}
			}
		}
	}
}
